#include <iostream>
#include <vector>
#include <cmath>
#include <string>

using namespace std;

const int INF = INT_MAX;

int getNod(int a, int b) {
    if (a == INF || a == 0) return b;
    if (b == INF || b == 0) return a;
    
    a = a > 0 ? a : (-1) * a ;
    b = b > 0 ? b : (-1) * b ;
    
    while (a > 0 && b > 0) {
          if (a > b ) { a = a - (a / b) * b; }
          else { b = b - (b / a) * a; }
    }

    return a > 0 ? a : b ;
}

void buildTree(vector<int>& tree, int size) {
    int logN = (int)(log((double)(size - 1)) / log(2.0));
    int n = (1 << (logN + 1));
    tree.resize(2 * n, INF);

    int onN = tree[n];

    for (int i = n ; i < 2 * n; i++) {
        tree[i] = tree[i - n + 1];
    }
    tree[2*n - 1] = onN;

    for (int i = n - 1; i > 0; i--) {
        tree[i] = getNod(tree[2 * i], tree[2 * i + 1]);
    }
}

int getRmq(vector<int>& tree, int l, int r){
    int ans = INF;
    int n = tree.size() / 2;

    l += n - 1, r += n - 1;

    while (l <= r){
        if (l & 1) {
            ans = getNod(ans, tree[l]);
        }

        if (!(r & 1)) {
            ans = getNod(ans, tree[r]);
        }

        l = (l + 1) / 2, r = (r - 1) / 2;
    }

    return ans;
}

void updateTree(vector<int>& tree, int indx, int val){
    int n = tree.size() / 2;
    indx += n - 1;

    tree[indx] = val;
    while (indx /= 2){
        tree[indx] = getNod(tree[2*indx], tree[2*indx + 1]);
    }
}

int main() {
    vector<int> tree;
    int n, a, b;
    cout<<"Input array size: ";
    cin>>n;
    cout<<endl<<"Input array: ";
    tree.push_back(0);

    for (int i = 0; i < n; ++i) {
        cin>>a;
        tree.push_back(a);
    }
    cout<<endl;
    buildTree(tree, n);

    cout<<"Commands:\n\tget l r \t- return NOD(array[l - 1], ... , array[r - 1])";
    cout<<"\n\tupdate i v \t- set array[i - 1] = v";
    cout<<"\n\texit \t\t- exit program\n\n";

    string command;
    while (true) {
        cout<<"Input command: ";
        cin>>command;

        if (command == "get") {
            cin>>a>>b;
            if (a > 0 && b <= n ) {
                cout<<"Nod = "<<getRmq(tree, a, b)<<endl<<endl;
            } else {
                cout<<"Error: index out of range"<<endl<<endl;
            }
            continue;
        }

        if (command == "update") {
            cin>>a>>b;
            updateTree(tree, a, b);
            cout<<endl;
            continue;
        }

        if (command == "exit") {
            exit(0);
        }

        cout<<"Unknown command"<<endl<<endl;
    }

    return 0;
}

